package com.wj.algorithm.dynamic.knapsack;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author Smile.Wu
 * @date 2016年4月6日  上午9:58:48
 */
public class KnapsackAlgorithm {
	/*
	 * 总容量
	 * 
	 * 本次规划所能承受的最大代价
	 */
	private int copacity;
	/*
	 * 总物品数
	 * 
	 * 选择，选择包含两个内容：代价、收益
	 */
	private int itemCount;

	private int index = 0;
	
	/*
	 * 二维数组
	 * 第一维：表示每个物品进入规划时，对应的最优规划值
	 * 第二维：表示空间容量从1递增至最大值，每个值对应可获得的最优值（收益）
	 */
	private int[][] dynamicArray;
	
	private Map<Integer, KnapsackItem> temp = null;
	
	public KnapsackAlgorithm(int copacity, int itemCount) {
		super();
		this.copacity = copacity;
		this.itemCount = itemCount;
		dynamicArray = new int[itemCount][copacity + 1];
		temp = new HashMap<>(itemCount);
	}

	public int getCopacity() {
		return copacity;
	}

	public void setCopacity(int copacity) {
		this.copacity = copacity;
	}
	
	/**
	 * 
	 * 插入一个备选项 <br>
	 * 插入一个备选项进行二位数组动态数据计算
	 *
	 * @param item
	 * @see [相关类/方法](可选)
	 * @since [产品/模块版本](可选)
	 */
	public void insertKnapsackItem(KnapsackItem item) {
		if(index < itemCount) {   //只有物品数量没达到规定时，才可以继续添加、计算
			temp.put(index, item);
			int itemSize = item.getSize();   //物品对应的代价，这里是占用的空间
			int itemValue = item.getValue();     //物品对应的价值，这里是对应的价值
			int[] temp = dynamicArray[index];
			int[] prevArray;
			if(index > 0) {
			    //如果之前已经有物品加入，则  prevArray 记录了上一个数组的空间规划动态值
				prevArray = dynamicArray[index - 1];
			} else {
			    //否则初始化一个空的空间规划数组
				prevArray = new int[copacity + 1];
			}
			
			//处理当前物品进入规划时，计算对应的空间规划数组
			for(int i = 1; i <= copacity; i ++) {
				int prevArrValue = prevArray[i];
				if(i >= itemSize) {
					
					int leftSize = i - itemSize;//i代表的空间减去物品消耗的空间，得到剩余空间
					/*
					 * 上一个物品对应的数组，已经是当时的最优解，因此直接从上个值数组中，获取剩余空间的最大可能值
					 */
					int leftSizeMaxValue = calculateMaxValue(prevArray, Math.min(leftSize, i - 1));
					
					//新的值（新收益）
					int newValue = itemValue + leftSizeMaxValue;
					//新值超过上一次存放的值（上一个选择进入规划后的最大收益），则生成新的最优值
					if(newValue > prevArrValue) {//超过上一次存放的价值
						temp[i] = newValue;
					} else {
						temp[i] = prevArrValue;
					}
				} else if(index > 0) {
				    //如果是当前处理的空间之小于物品代价，则当前物品对应的空间数组并没有发生变化，与上一级相同，复制上一级的空间规划数组对应值
					temp[i] = prevArrValue;
				}
			}

			index ++;
		}
	}
	
	public List<KnapsackItem> best() {
		List<KnapsackItem> rs = new ArrayList<>();

        int startCopacity = copacity;
        for(int i = itemCount; i > 0; i --) {   //从最后一个开始筛选
            int currentIndex = i - 1;
            if(currentIndex == 0 || dynamicArray[currentIndex][startCopacity] > dynamicArray[currentIndex - 1][startCopacity]) {
                //符合条件
                KnapsackItem item = temp.get(currentIndex);
                if(item != null) {
                    rs.add(item);
                    startCopacity -= item.getSize();
                }
            }
        }
		
		return rs;
	}

	/*
	 * 在指定的数组arr中，寻找maxSize位置之前的最大值
	 */
	public int calculateMaxValue(int[] arr, int maxSize) {
		int tempValue = 0;
		for(int i = 0, len = arr.length; i <= maxSize && i < len; i ++) {
			int value = arr[i];
			if(value > tempValue) {
				tempValue = value;
			}
		}
		return tempValue;
	}
	
	public void showArray(){
		boolean isTitle = false;
		for(int i = 0, ilen = dynamicArray.length; i < ilen; i ++) {
			int[] temp = dynamicArray[i];
			if(!isTitle) {
				for(int j = 0, jlen = temp.length; j < jlen; j ++) {
					System.out.print(j + "\t");
				}
				isTitle = true;
				System.out.println();
			}
			
			for(int j = 0, jlen = temp.length; j < jlen; j ++) {
				System.out.print(temp[j] + "\t");
			}
			System.out.println();
		}
	}
	
	public static void main(String[] args) {
		List<KnapsackItem> list = new ArrayList<>();
		list.add(new KnapsackItem(5, 20));
		list.add(new KnapsackItem(4, 10));
		list.add(new KnapsackItem(3, 12));
//		list.add(new KnapsackItem(1, 1100));
//		list.add(new KnapsackItem(6, 6700));
		
		KnapsackAlgorithm algorithm = new KnapsackAlgorithm(10, list.size());
		for(KnapsackItem item : list) {
			algorithm.insertKnapsackItem(item);
		}
		
		algorithm.showArray();
		System.out.println();
		List<KnapsackItem> result = algorithm.best();
		for(KnapsackItem item : result) {
			System.out.println(item.getSize() + " : " + item.getValue());
        }
    }
}
